#include <iostream>

struct Node {
    int val;
    Node *left;
    Node *right;
};

struct List {
    List(Node *h, Node *t) {
        head = h;
        tail = t;
    }
    Node *head;
    Node *tail;
};

List tree_to_list(Node *root)
{
    if (root == NULL) {
        return List(NULL, NULL);
    }

    List _left = tree_to_list(root->left);
    List _right = tree_to_list(root->right);

    List res(_left.head, _right.tail);

    if (_left.tail != NULL) {
        _left.tail->right = root;
        root->left = _left.tail;
    } else {
        res.head = root;
    }

    if (_right.head != NULL) {
        _right.head->left = root;
        root->right = _right.head;
    } else {
        res.tail = root;
    }

    return res;
}

void change(Node *p, Node *&last) //中序遍历
{
    if (p == NULL) {
        return;
    }

    change(p->left, last);

    if (last) {
        last->right = p;
    }

    p->left = last;

    last = p;
    change(p->right, last);
}

void link(Node nodes[], int t, int l, int r)
{
    if (l != -1) {
        nodes[t].left = &nodes[l];
    }

    if (r != -1) {
        nodes[t].right = &nodes[r];
    }
}

int main(int argc, const char *argv[])
{
    {
        //测试一
        Node nodes[] = {
            {1, NULL, NULL},
            {2, NULL, NULL},
            {3, NULL, NULL},
            {4, NULL, NULL},
            {5, NULL, NULL},
            {6, NULL, NULL},
            {7, NULL, NULL}
        };

        link(nodes, 0, 1, 2);
        link(nodes, 1, 3, 4);
        link(nodes, 2, 5, 6);

        List rs = tree_to_list(nodes);
        Node *head = rs.head;

        while (head != NULL) {
            std::cout << head->val << " ";
            head = head->right;
        }

        std::cout << std::endl;
    }
    {
        //测试二
        Node nodes[] = {
            {1, NULL, NULL},
            {2, NULL, NULL},
            {3, NULL, NULL},
            {4, NULL, NULL},
            {5, NULL, NULL},
            {6, NULL, NULL},
            {7, NULL, NULL}
        };

        link(nodes, 0, 1, 2);
        link(nodes, 1, 3, 4);
        link(nodes, 2, 5, 6);

        Node *head = nodes;
        Node *tail = NULL;
        change(head, tail);

        while (tail != NULL && tail->left != NULL) {
            std::cout << tail->val << " ";
            tail = tail->left;
        }

        std::cout << tail->val << std::endl;
        Node *p = tail;

        while (p != NULL && p->right != NULL) {
            std::cout << p->val << " ";
            p = p->right;
        }

        std::cout << p->val << std::endl;
    }

    return 0;
}
